package com.ly.algorithm.leetcode.array;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @Classname Problem90
 * @Description
 *
 * 给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
 *
 * 说明：解集不能包含重复的子集。
 *
 * 示例:
 *
 * 输入: [1,2,2]
 * 输出:
 * [
 *   [2],
 *   [1],
 *   [1,2,2],
 *   [2,2],
 *   [1,2],
 *   []
 * ]
 *
 *
 * @Date 2020/12/9 11:20
 * @Author 冷心影翼
 */
public class Problem90 {

	public static void main(String[] args) {
		Solution90 solution90 = new Solution90();
		List<List<Integer>> lists = solution90.subsetsWithDup(new int[]{4,4,4,1,4});
		List<List<Integer>> lists2 = solution90.subsetsWithDupBest(new int[]{4,4,4,1,4});

		System.out.println(lists);
		System.out.println(lists2);
	}
}


class Solution90 {
	public List<List<Integer>> subsetsWithDup(int[] nums) {
		Set<List<Integer>> lists = new HashSet<>();
		lists.add(new ArrayList<>());
		Arrays.sort(nums);
		for(int i=0;i<nums.length;i++) {
			Iterator<List<Integer>> iterator = lists.iterator();
			int length = lists.size();
			Set<List<Integer>> set2 = new HashSet<>();
			for(int j=0;j<length;j++) {
				List<Integer> list = new ArrayList<>(iterator.next());
				list.add(nums[i]);
				set2.add(list);
			}
			lists.addAll(set2);
		}
		List<List<Integer>> collect = lists.stream().collect(Collectors.toList());
		return collect;
	}


	//   1,2,2,2,3
	//[] [1]   0
	//[] [1] [2] [1,2]  2
	//[] [1] [2] [1,2] [2] [1,2] [2,2] [1,2,2]  4
	//
	public List<List<Integer>> subsetsWithDupBest(int[] nums) {
		List<List<Integer>> lists = new ArrayList<>();
		lists.add(new ArrayList<>());
		Arrays.sort(nums);
		int left;
		int right;
		int length = 0;
		for(int i=0;i<nums.length;i++) {
			if(i>0 && nums[i-1] == nums[i]) {
				left = lists.size() - length;
			}else {
				left = 0;
			}
			right = lists.size();
			length = right - left;
			for(int j=left;j<right;j++) {
				ArrayList<Integer> list = new ArrayList<>();
				list.addAll(lists.get(j));
				list.add(nums[i]);
				lists.add(list);
			}
		}
		/*
		for(int i=0;i<nums.length;i++) {
			int length = lists.size();
			for(int j=0;j<length;j++) {
				ArrayList<Integer> list = new ArrayList<>();
				list.addAll(lists.get(j));
				list.add(nums[i]);
				if(!lists.contains(list)) {
					lists.add(list);
				}
			}
		}
		*/
		return lists;
	}
}